This invention relates to solving linear assignment problems often arising for combinational layout problems in integrated circuit design, such as routing and pin and buffer assignment.
Linear assignment problems are employed to solve and optimize combinational layout problems for integrated circuit design. For example, combinational channel routing layouts, pin positioning and buffer assignments are often treated as linear assignment problems of placing objects in an ordered system of boxes. Assignment problems are used to locate, in an undirected graph G, a match M that is a subset of an edge E, M  E, such that no vertex is incident to more than one edge. The linear assignment problem assumes that graph G is complete with edge weights, and seeks a perfect match of minimum weight. The match is called xe2x80x9cperfectxe2x80x9d if each vertex is incident to exactly one edge.
Integrated circuit design often poses problems of assigning objects to boxes with minimal penalties where the number of object/box combinations exceeds 106. Classical linear assignment problems are ineffective where the number of objects and boxes of the problem reach 104 to 106 or more. Consequently, it was common to reduce the problem to more manageable pieces and solve each piece individually. The solved pieces were re-assembled, and adjustments were made to the solution. However, the reduction and re-assembly processes were difficult, and often introduced unexpected cost functions to the solution. There is, accordingly, a need for a more effective solution to linear assignment problems that can handle large numbers of combinational assignments, such as for use in integrated circuit layout design.
The present invention provides an effective solution of the linear assignment problem for an ordered system of boxes with linear topology and with unimodal penalty functions for objects.
The present invention provides a process for optimizing a layout of objects in an ordered system of boxes with minimal penalty from a collection of boxes containing the objects. A hierarchy is created containing a top level, a bottom level and one or more intermediate levels. The bottom level contains at least as many generalized boxes as original boxes in the assignment problem. The top and intermediate levels each contains an integer number       n    2    ⁢      xe2x80x83    ⁢  or  ⁢      xe2x80x83    ⁢            n      +      1        2  
generalized boxes where n is the integer number of generalized boxes in the next lower level. The top level contains one generalized box. All objects of the assignment problem are placed in the generalized box of the top level. A first local task is executed to transition the contents of a generalized box of a higher level to at least two generalized boxes of the next lower level. A second local task is executed to the contents of a plurality of generalized boxes of lower level to minimize a global penalty function. Thereafter, the first and second tasks are executed through successive iterations until all of the objects are placed in the boxes of the bottom level in a layout having minimal penalty function.
In one form, the invention is manifest in a computer readable program containing code that, when executed by a computer, causes the computer to perform the process steps to layout the objects.